package com.base;

import java.util.HashMap;

/**
 * @author: sun.hongliang
 * @create: 2019/08/10 14:21
 */
public class LRU<K, V> {
    private final int MAX_CACHE_SIZE;
    private Entry<K, V> head;
    private Entry<K, V> tail;
    private HashMap<K, Entry<K, V>> cache;
    
    public LRU(int MAX_CACHE_SIZE) {
        this.MAX_CACHE_SIZE = MAX_CACHE_SIZE;
        cache = new HashMap<>(MAX_CACHE_SIZE);
    }

    private static class Entry<K, V> {
        Entry<K, V> pre;
        Entry<K, V> next;
        K key;
        V value;
    }

    public void put(K key, V value) {
        Entry<K, V> entry = getEntry(key);
        if (entry == null) {
            if (cache.size() >= MAX_CACHE_SIZE) {
                cache.remove(tail.key);
                removeTail();
            }
            entry = new Entry<>();
            entry.key = key;
            entry.value = value;
            moveToHead(entry);
            cache.put(key, entry);
        } else {
            entry.value = value;
            moveToHead(entry);
        }
    }

    public V get(K key) {
        Entry<K, V> entry = getEntry(key);
        if (entry == null) {
            return null;
        }
        moveToHead(entry);
        return entry.value;
    }

    private void removeTail() {
        if (tail != null) {
            Entry<K, V> prev = tail.pre;
            if (prev == null) {
                head = null;
                tail = null;
            } else {
                tail.pre = null;
                tail = prev;
                tail.next = null;
            }
        }
    }

    private void moveToHead(Entry<K, V> entry) {
        if (entry == head) {
            return;
        }
        if (entry.pre != null) {
            entry.pre.next = entry.next;
        }
        if (entry.next != null) {
            entry.next.pre = entry.pre;
        }
        if (entry == tail) {
            Entry<K, V> prev = entry.pre;
            if (prev != null) {
                tail.pre = null;
                tail = prev;
                tail.next = null;
            }
        }

        if (head == null || tail == null) {
            head = tail = entry;
            return;
        }

        entry.next = head;
        head.pre = entry;
        entry.pre = null;
        head = entry;
    }

    private Entry<K, V> getEntry(K key) {
        return cache.get(key);
    }
}
